#include <stdio.h>
#include <stdlib.h>

/**
 * 单向链表实现队列，队尾插入，队头取出
 * 队头指向一个占位元素，队尾指向最后插入的节点
 * 每次取队头元素时，是取队头的next元素
 * 实现的功能如下：
 * 1. 创建链表
 * 2. 入队
 * 3. 出队
 * 4. 取出队头元素
 * 5. 判断队列是否为空
 * 6. 清空队列
 * 7. 销毁队列
 * 8. 打印队列
 */

typedef int data_t;
typedef struct link_node {
    data_t data;
    struct link_node *next;
} link_node_t;

typedef struct queue {
    struct link_node *head;
    struct link_node *tail;
} queue_t;

queue_t *create_queue() {
    queue_t *q;
    q = malloc(sizeof(queue_t));
    q->head = malloc(sizeof(link_node_t));
    q->head->next = NULL;
    q->tail = q->head;
    return q;
}

int in_queue(queue_t *q, data_t *d) {
    link_node_t *ln;

    ln = malloc(sizeof(link_node_t));
    ln->data = *d;
    ln->next = NULL;
    q->tail->next = ln;
    q->tail = ln;

    return 0;
}

int out_queue(queue_t *q, data_t *response) {
    link_node_t *tmp;

    if(q->head == q->tail) return -1;
    if(NULL == q->head) return -1;

    tmp = q->head->next;
    q->head->next = q->head->next->next;
    *response = tmp->data;
    free(tmp);

    return 0;
}

int get_head_queue(queue_t *q, data_t *response) {
    *response = q->head->next->data;
    return 0;
}

int is_empty_queue(queue_t *q) {
    return NULL == q->head->next ? 1 : 0;
}

//清空队列，意味着头元素还存在，将tail指向头
int clean_queue(queue_t *q) {
    link_node_t *t1, *t2;
    t1 = q->head->next;
    while(NULL != t1) {
        t2 = t1;
        t1 = t1->next;
        free(t2);
    }
    q->head->next = NULL;
    q->tail = q->head;
    return 0;
}

int destory_queue(queue_t **qq) {
    //将队列恢复至初始状态
    clean_queue(*qq);
    //释放头元素的内存
    free((*qq)->head);
    //释放队列内存
    free((*qq));
    //将队列指针置为NULL
    *qq = NULL;

    return 0;
}

void print_queue(queue_t *q) {
    link_node_t *tmp;
    tmp = q->head;
    printf("当前队列为：");
    while(NULL != tmp->next) {
        printf("%d ", tmp->next->data);
        tmp = tmp->next;
    }
    printf("\n");
}

int main(int argc, const char *argv[]) 
{
    queue_t *q;
    data_t *response;
    q = create_queue();
    int i;
    for(i = 0; i < 10; i++) {
        in_queue(q, &i);
    }
    print_queue(q);

    out_queue(q, response);
    printf("出队：%d\n", *response);

    out_queue(q, response);
    printf("出队：%d\n", *response);

    out_queue(q, response);
    printf("出队：%d\n", *response);

    print_queue(q);

    get_head_queue(q, response);
    printf("获取队顶元素：%d\n", *response);

    clean_queue(q);
    printf("清空队列后，判断队列是否为空：%d\n", is_empty_queue(q));

    printf("重新加入数据：\n");
    for(i = 0; i < 10; i++) {
        in_queue(q, &i);
    }
    print_queue(q);

    /*
    //此处有bug
    destory_queue(&q);
    if(NULL == q) {
        printf("队列已销毁成功\n");
    } else {
        printf("队列已销毁失败\n");
    }
    */

}

